/*
32. 最长有效括号
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
示例 3：

输入：s = ""
输出：0


提示：

0 <= s.length <= 3 * 104
s[i] 为 '(' 或 ')'
*/
package main

import "fmt"

func longestValidParentheses(s string) int {
	/*0123456789ab
	((())()()())
	000000000000
	0002406080ac

	*/
	n := len(s)
	if n < 2 {
		return 0
	}
	max := 0
	array := make([]int, n)
	for i := 1; i < n; i++ {
		if s[i] == ')' { // 括号结束
			if s[i-1] == '(' { // 连续的()
				if i > 2 {
					array[i] = array[i-2] + 2 // 后续的()
				} else {
					array[i] = 2 // 开始的()
				}
			} else if i-array[i-1] > 0 && s[i-array[i-1]-1] == '(' { // s[i-array[i-1]-1]  找到开始的地方
				if i-array[i-1] >= 2 {
					array[i] = array[i-1] + array[i-array[i-1]-2] + 2 //"()(())"  i=5
				} else {
					array[i] = array[i-1] + 2
				}
			}
		}
		if array[i] > max {
			max = array[i]
		}
	}
	return max

}

func test(s string) {
	fmt.Printf("字符串%s最长有效括号长度为%d\n", s, longestValidParentheses(s))
}
func main() {
	inputs := []string{
		"(()",
		")()())",
		"",
		"()(()",
		"()(())",
		"(()()",
		"(()())",
		"((())()()())",
		"(())(())(())()",
	}
	for _, s := range inputs {
		test(s)
	}

}
